using System;
using System.Text;

namespace DataStructure
{
    public class LinkedList1<T>
    {
        private class Node
        {
            public T data; //实际存储的数据
            public Node next; //指向下一个节点的引用
            
            public Node(T data,Node next)
            {
                this.data = data;
                this.next = next;
            }
            //默认构造函数
            public Node(T data)
            {
                this.data = data;
                this.next = null;
            }

            public override string ToString()
            {
                return data.ToString(); 
            }
        }
        
        private Node head; //头节点
        private int size; //链表长度
        
        //默认构造函数,head->null
        public LinkedList1()
        {
            head = null;
            size = 0;
        }
        
        //定义属性,获取链表长度
        public int Count => size;
        //判断链表是否为空
        public bool IsEmpty => size == 0;
        
        //添加元素
        public void Add(int index ,T data)
        {
            if (index < 0 || index > size)
                throw new ArgumentException("非法索引");   
                
            //操作索引为0
            if (index == 0)
            {
                Node node = new Node(data);
                node.next = head;
                head = node;
                //既head = new Node(data,head);
            }
            else
            {
                Node pre = head;
                //让pre指向插入位置
                for (int i = 0; i < index-1; i++)
                    pre = pre.next;
                    
                Node node = new Node(data);
                node.next = pre.next;
                pre.next = node;
            }
            size++;
        }
        //头尾添加
        public void AddFirst(T data) => Add(0, data);
        public void AddLast(T data) => Add(size, data);
        
        //删除元素(根据索引)
        public T RemoveAt(int index)
        {
            if (index < 0 || index >= size)
                throw new ArgumentException("非法索引");
            
            //删除头结点
            if(index == 0)
            {   
                Node delNode = head;
                head = head.next;
                size--;
                return delNode.data;
            }
            else
            {
                Node pre =  head;
                for (int i = 0; i < index - 1; i++)
                    pre = pre.next;

                Node delNode = pre.next;
                pre.next = delNode.next;
                size--;
                return delNode.data;
            }  
        }
        //删除头尾
        public T RemoveFirst() => RemoveAt(0);
        public T RemoveLast() => RemoveAt(size - 1);
        
        //通过查找元素删除
        public void Remove(T data)
        {
            //空链直接退出
            if (head == null)
                return;
            //判断头结点是否为data
            if(head.data.Equals(data))
            {
                head = head.next;
                size--;
            }
            else
            {
                Node cur = head;    //指向头结点
                Node pre = null;    //指向待删除结点
                
                while (cur != null)
                {
                    if(cur.data.Equals(data))
                        break; //找到data,退出循环
                    pre = cur;
                    cur = cur.next;
                }
                if(cur != null)
                {
                    pre.next  = pre.next.next;
                    size--;
                }
            }
        }
        //查找元素(依据索引)
        public T Get(int index)
        {
            if (index < 0 || index >= size)
        	   throw new ArgumentException("非法索引");
        	   
        	Node cur = head;
        	for (int i = 0; i < index; i++)
        	   cur = cur.next;
        	
        	return cur.data;
        }
        //获取头尾元素
        public T GetFirst() => Get(0);
        public T GetLast() => Get(size - 1);
        
        //修改元素
        public void Set(int index, T newData)
        {
            if (index < 0 || index >= size)
        	   throw new ArgumentException("非法索引");
        	   
        	Node cur = head;
        	for (int i = 0; i < index; i++)
        	   cur = cur.next;

        	cur.data = newData;
        }
        
        //是否包含元素
        public bool Contains(T data)
        {   
            Node cur = head;
            while (cur != null)
            {
                if(cur.data.Equals(data))
                    return true;
                cur = cur.next;
            }
            return false;
        }
        //重写ToString用于测试
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            Node cur = head;
            while (cur != null)
            {
                sb.Append(cur.data + "->");
                cur = cur.next;
            }
            sb.Append("NULL");
            return sb.ToString();
        }
    }
}